package com.cn.algorithm02.class23;

/***
 * @author: hels
 * @description:
 * 给定一个正数1，裂开的方法有一种，(1)
 * 给定一个正数2，裂开的方法有两种，(1和1)、(2)
 * 给定一个正数3，裂开的方法有三种，(1、11)、(1、2)(3)
 * 给定一个正数4，开方法有五种(1、1、1、1)、(1、1、2)、(1、3)、(2、2)、(4)
 * 给定一个正数n，求裂开的方法数。
 * 规定后边的数不能比前边的小
 * 动态规划优化状态依赖的技巧
 **/
public class C03_SplitNumber {
    public static int right(int num) {
        if (num <= 0) {
            return 0;
        }
        return process(1, num);
    }

    /** 暴力递归 */
    private static int process(int pre, int rest) {
        if (rest == 0) {
            return 1;
        }
        if (pre > rest) {
            return 0;
        }
//        if (pre == rest) {
//            return 1;
//        }
        int ways = 0;
        for (int current = pre; current <= rest; current++) {
            ways += process(current, rest - current);
        }
        return ways;
    }

    /**
     *  二位数组的动态规划
     */
    public static int dp(int num ) {
        if (num <= 0) {
            return 0;
        }
        int[][] dp = new int[num + 1][num + 1];
        for (int pre = 1; pre <= num; pre++) {
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        for (int pre = num - 1; pre >= 1; pre--) {
            for (int rest = pre + 1; rest <= num; rest++) {
                int ways = 0;
                for (int current = pre; current <= rest; current++) {
                    ways += dp[current][ rest - current];
                }
                dp[pre][rest] = ways;
            }
        }
        return dp[1][num];
    }

    /**
     *  二位数组的动态规划
     */
    public static int dp2(int num ) {
        if (num <= 0) {
            return 0;
        }
        int[][] dp = new int[num + 1][num + 1];
        for (int pre = 1; pre <= num; pre++) {
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        for (int pre = num - 1; pre >= 1; pre--) {
            for (int rest = pre + 1; rest <= num; rest++) {
                // 此处枚举转规律，需要画出二位表，举例找出规律
                dp[pre][rest] += dp[pre + 1][rest];
                dp[pre][rest] += dp[pre][rest - pre];
            }
        }
        return dp[1][num];
    }


    public static void main(String[] args) {
        int num = 39;
        System.out.println(right(num));
        System.out.println(dp(num));
        System.out.println(dp2(num));
    }
}
